package leetcode_1000;

/**
 *@author 周杨
 *FlipStringToMonotoneIncreasing_926_
 *describe:
 *2018年10月21日 下午2:36:02
 */
/**
 *@author 周杨
 *FlipStringToMonotoneIncreasing_926_ 一个二进制字符串 0可以翻成1  1可以翻成0 问最少多少次反转能使字符串变成升序字符串
 *describe:用动态规划 记录状态 
 *2018年10月21日 下午2:43:01
 */
public class FlipStringToMonotoneIncreasing_926_ {
	public static void main(String[] args) {
		FlipStringToMonotoneIncreasing_926_ test=new FlipStringToMonotoneIncreasing_926_();
		System.out.println(test.minFlipsMonoIncr("1"));
		System.out.println(test.minFlipsMonoIncr("00110"));
		System.out.println(test.minFlipsMonoIncr("010110"));
		System.out.println(test.minFlipsMonoIncr("00011000"));
	}
	
	public int minFlipsMonoIncr(String S) {
		if (S.length() == 0)
			return 0;
		char [] chars=S.toCharArray();
		int dp0=0,dp1=0,min;
		if(chars[0]=='0')
			dp1=1;
		else
			dp0=1;
		for(int i=1;i<chars.length;++i) {
			min=Math.min(dp0, dp1);
			if(chars[i]=='0') {
				//dp0不变
				dp1=min+1;
			}
			else {//1
				dp0++;//翻1
				dp1=min;
			}
		}
		return Math.min(dp0, dp1);
	}
	
	public int minFlipsMonoIncr2(String S) {
		if (S.length() == 0)
			return 0;
		int[][] dp = new int[S.length()][2];
		dp[0][0] = S.charAt(0) == '1' ? 1 : 0;
		dp[0][1] = S.charAt(0) == '0' ? 1 : 0;
		for (int i = 1; i < S.length(); i++) {
			if (S.charAt(i) == '1') {
				dp[i][0] = dp[i - 1][0] + 1;
				dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]);
			} else {
				dp[i][0] = dp[i - 1][0];
				dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
			}
		}
		return Math.min(dp[S.length() - 1][0], dp[S.length() - 1][1]);
	}
	
	
	/**
	 * describe:思想错误 
	 * 2018年10月21日 上午10:30:51
	 */
	public int minFlipsMonoIncr1(String S) {
        char[] chars=S.toCharArray();
        int index=0;
        while(index<chars.length&&chars[index]=='0') ++index;//把前面的0过滤掉
        int count1=0,count0=0;
        while(index<chars.length) {
        	//从1开始遍历
        	int run=index;
        	while(run<chars.length&&chars[run]=='1') ++run;
        	count1+=run-index;
        	index=run;
        	while(run<chars.length&&chars[run]=='0') ++run;
        	count0+=run-index;
        	index=run;
        }
        return Math.min(count0, count1);
    }
}
